1. Field of the Invention
The present invention relates to a network system having a network device using an associative memory and, in particular, to an associative memory having a mask function.
2. Description of the Prior Art
The function that compares the length of the significant part between network addresses to thereby calculate an optimal destination taking it into account is indispensable to a conventional network device (for example a router) in a computer network system, and an associative memory is used in order to achieve this function.
Referring to FIG. 11, a conventional computer network will be described. A user or subscriber of the network has a user's terminal, such as a computer terminal, for connection to the network. A user's terminal is assigned with a specific network address in accordance with a predetermined rule when it is connected to the network in order to be distinguished from other user's terminals. Herein, the network address is represented by a numeral of a plurality of digits of, for example, first through third digits (a.b.c). The predetermined rule defines a hierarchical structure of the network address, for example, the first digit of the numeral represents a nation, such as England, Germany, and Japan, and the second digit of the numeral represents a company name in the nation. In the following description, these hierarchical items will be called segments. Referring to FIG. 11, each segment is depicted by a hierarchical structure. In the view, one rectangle surrounded by a thick line represents one segment. Specifically, the network includes a first segment (SEGMENT1), second segment (SEGMENT2), and a third segment (SEGMENT3) at a highest hierarchical level in FIG. 11. The first segment (SEGMENT1), the second segment (SEGMENT2), and the third segment (SEGMENT3) include a fourth segment (SEGMENT4) and a fifth segment (SEGMENT5), a sixth segment (SEGMENT6), and a seventh segment (SEGMENT7), respectively. A user's terminal 401-1 exists in the fourth segment. The first segment has a network address (1.*.*) in which a first digit alone is specified as “1”. The fourth segment subordinate to the first segment has a network address (1.2.*) in which first and second digits “1” and “2” are specified. The fifth segment subordinate to the first segment has a network address (1.3.*) in which first through second digits “1” and “3” are specified. Thus, the user's terminal 401-1 in the fourth segment has a specific or unique network address (1.2.6). The second segment has a network address (2.*.*) in which a first digit alone is specified as “2”. The sixth segment subordinate to the second segment has a network address (2.6.*) in which first and second digits “2” and “6” are specified. User's terminals 401-2 and 401-3 exist in the sixth segment. The sixth segment subordinate to the second segment has a network address (2.6.*) in which first and second digits “2” and “6” are specified. Thus, the user's terminals 401-2 and 401-3 in the sixth segment have specific or unique network addresses (2.6.4) and (2.6.5), respectively. Further, the third segment has a network address (3.*.*) in which a first digit alone is specified as “3”. The seventh segment subordinate to the third segment has a network address (3.2.*) in which first and second digits “3” and “2” are specified. A symbol “*” contained in these addresses represents “don't care”.
Each digit of each network address is represented by a binary number of three bits. Thus, each network address is represented by a bit sequence of nine bits in total. For example, a network address (1.2.*) is represented by a binary bit sequence (001.010.000). Hereinafter, a bit sequence represented as above-mentioned representation is called a storage data. Since the symbol “*” represents “don't care” for a third digit, it is necessary to indicate that the first through the sixth bits (001.010) in the bit sequence (001.010.000) alone are valid and the remaining bits (000) are invalid. For this purpose, mask information (or mask data) is combined with the storage data. Hereinafter, this pair is called structured data. In said example, the corresponding mask information is given by a bit sequence “111.111.000” in binary numbers notation. Herein, “1” and “0” represent a mask invalid state and a mask valid state, respectively.
In order to connect or establish communication between a plurality of user's terminals in the network, each segment is provided with a network device. As illustrated in FIG. 11, the first segment is provided with the first network device 400-1, the second segment is provided with the second network device 400-2, the third segment is provided with the third network device 400-3, the forth segment is provided with the forth network device 400-4, the fifth segment is provided with the fifth network device 400-5, the sixth segment is provided with the sixth network device 400-6, and the seventh segment is provided with the seventh network device 400-7. As illustrated in FIG. 11, each network device is connected to any network devices or any user's terminals subordinate to the corresponding segment. In addition, the network device 400-1 is also connected to the network device 400-2, the network device 400-3, and the network device 400-6.
Each network device in the corresponding segment is supplied from any user's terminals or any network devices connected to the network device with transfer data and a destination network address annexed thereto. With reference to the destination network address and the relationship of connection of network devices, the network device calculates an optimum transfer route and transfers the transfer data via the optimum transfer route thus calculated.
Herein, when the network device 400-1 transfers communication data where the destination network address corresponding to the user's terminal 401-2 is (2.6.4) in FIG. 11, as is understood from the drawing, it is most suitable to transfer the communication data to the network device 400-6 corresponding to the network address (2.6.*) which shows the segment 6 rather than transferring the communication to the network device 400-2 corresponding to the network address (2.*.*) which shows the segment 2. It will therefore be understood that it is most suitable to select a network device corresponding to a network address with mask information having the least number, of bits in a valid state for the mask information among network addresses coincident with the destination network address taking the mask information into account.
Thus, the user's terminals are not directly connected by the use of the communication channels but carry out communication by controlling the transfer of the transfer data by the use of the network devices. Thus, communication channels as limited resources are saved.
Next, referring to FIG. 12, description will be directed to calculating the transfer network address of these conventional network devices. In the drawing, although the network device 400-1 is illustrated by way of example, other network devices have a similar structure. A destination network address annexed to the transfer data supplied to the network device 400-1 is supplied to a conventional associative memory 100 as search data 101. The conventional associative memory 100 stores network addresses which show segments, to which network devices 400-2, 400-3, 400-4, 400-5 and 400-6 connected to the network device 400-1 belong, in the form of the above-mentioned structured data. Therefore, in the example in FIG. 12, a primary associative memory word 109-1 stores the network address (2.*.*) for the segment 2 to which the network device 400-2 belongs in the form of structured data represented by a pair of the storage data “010.000.000” and the mask information “11.000.000” as mentioned above. Similarly, a primary associative memory word 109-2, a primary associative memory word 109-3, a primary associative memory word 109-4, and a primary associative memory word 109-5 store the network address (3.*.*) for the segment 3 to which the network device 400-3 belongs, the network address (1.2.*) for the segment 4 to which the network device 400-4 belongs, the network address (1.3.*) for the segment 5 to which the network device 400-5 belongs and the network address (2.6.*) for the segment 6 to which the network device 400-6 belongs in the form of above-mentioned structured data, respectively.
The associative memory 100 has searching (or retrieving) function or mask searching function in addition to write/read functions of writing and reading storage data (namely, the address data) at a designated memory address in the matter similar to an ordinary memory circuit. Specifically, the associative memory 100 has the mask searching function to put the only match line 102 corresponding to the storage data with the least number of bits into a mask valid state, in the match lines 102 corresponding to one of the storage data coincident with the search data 101 taking the mask information into account, into a valid state. Formerly, an associative memory which has been disclosed in, for example Japanese Patent Application No. 3191737 or the like is known as this kind of associative memory 100.
An encoder 402 encodes the mask match lines 102-1 through 102-5 that the associative memory 100 supplies into a memory address signal 403. The memory 404 stores network addresses of the network devices corresponding to the segment network addresses each of which is stored in each of primary associative memory words 109-1 through 109-5 of the associative memory 100. In the memory 404, each network address of the network device is stored in a word corresponding to the associative memory words 109-1 through 109-5 of the associative memory 100 where a corresponding network address is stored. For example, the network address (2.*.*) is stored in the primary associative memory word 109-1 of the associative memory 100 while the network address of the network device 400-2 (FIG. 11) corresponding thereto is stored in the first word of the memory 404. Similarly, the network address of the network device 400-3, the network address of the network device 400-4, the network address of the network device 400-5, and the network address of the network device 400-6 are stored in the second word, the third word, the fourth word, and fifth word of the memory 404, respectively. Supplied with the memory address signal 403 as a read address, the memory 404 produces a memory data signal 405 stored in the word designated by the memory address signal 403. The memory data signal 405 is used as a new transfer network address of the transfer data.
Although not illustrated in the figure, each of network devices 400-1 through 400-7 has a CPU for controlling the above-mentioned operation of the network device.
Next, description will be made about an operation of the transfer network address calculation by the conventional network device in the network system. It is assumed here that the destination network address supplied to the network device 400-1 has a destination network address (2.6.5) corresponding to the user's terminal 401-3. As a result of search by the associative memory 100, (2.*.*) in the primary associative memory word 109-1 and (2.6.*) in the primary associative memory word 109-5 are coincident. Among those coincident network addresses, the network address (2.6.*) in the primary associative memory word 109-5 has the least number of bits in a mask valid state so that only the match line 102-5 corresponding to the primary associative memory word 109-5 is put into a valid state. Therefore, the encoder 402 produces “5” as the memory address signal 403. In response to the memory address signal 403, the memory 404 produces as the memory data signal 405 the network address (2.6.*) for the network device 400-6 stored in the fifth word. Consequently, the network device 400-1 transfers the input communication data including the destination network address (2.6.5) to the network device 400-6. The network device 400-6 is responsive to the transfer data and performs the operation similar to that mentioned above. Thus, the transfer data are successively transferred from a network device to a network device until the user's terminal 401-3 at the destination network address (2.6.5) is reached.
(Description of the Conventional Associative Memory)
Herein, referring to FIG. 13, a typical conventional associative memory will be described. The associative memory 100 of a first through m-th words n-bit configuration (m and n are integer variables) comprises an associative memory 103 for primary searching operation of a first through m-th words n-bit configuration, and an associative memory 104 for secondary searching operation of a first through m-th words n-bit configuration, and has primary bit lines 105-1 through 105-n supplied with the n-bit search data 101, and match lines 102-1 through 102-m, m in number for delivering the final result of the searching operation.
The associative memory 103 for primary searching operation of a first through m-th words n-bit configuration is supplied with the primary bit lines 105-1 through 105-n, and produces primary match lines 116-1 through 116-m and intermediate data lines 106-1 through 106-n. The associative memory 103 for primary searching operation comprises primary associative memory words 109-1 through 109-m which can store the structured data comprising the storage data and the mask information (or mask data), each being n-bit. The primary associative memory words 109-j (j is an integer variable between 1 and m, both inclusive) comprise data cells 110-j-1 through 110-j-n for storing the n-bit storage data and mask cells 111-j-1 through 111-j-n for storing the corresponding n-bit mask information. Herein, when a digit of the structured data is represented by the symbol “*” as “don't care”, the corresponding bit of the storage data is stored in the corresponding data cell 110 with an invalid state for the storage data, and the corresponding bit of the mask information is stored in the corresponding mask cell 111 with a valid state for the mask information. The associative memory 103 for primary searching operation carries out a primary searching operation to search storage data coincident with the primary bit lines 105-1 through 105-n taking the corresponding mask information into account, and puts a primary match line 116 corresponding to the primary associative memory word 109 which stores the coincident storage data into a valid state, and puts other primary match lines 116 into an invalid state. The associative memory 103 for primary searching operation also supplies a value obtained from a result of a logical sum operation (an OR operation), with a valid state for the storage data as true, of all the coincident storage data to the intermediate data lines 106-1 through 106-n. A state of the intermediate data lines 106-1 through 106-n is supplied to secondary bit lines 108-1 through 108-n as n-bit intermediate data 107.
The associative memory 104 for secondary searching operation of a first through m-th words n-bit configuration is supplied with the secondary bit lines 108-1 through 108-n, and produces secondary match lines 126-1 through 126-m. The associative memory 104 for secondary searching operation comprises secondary associative memory words 112-1 through 112-m which can store n-bit secondary storage data. A j-th secondary associative memory word 112-j has data cells 113-j-1 through 113-j-n for storing the n-bit secondary storage data. The associative memory 104 for secondary searching operation carries out a secondary searching operation to search secondary storage data coincident with the secondary bit line 108-1 through 108-n, and puts a secondary match line 126 corresponding to the secondary associative memory word 112 which stores the coincident secondary storage data into a valid state, and puts other secondary match lines 126 into an invalid state. A state of the secondary match lines 126-1 through 126-m is supplied to an external source as the match lines 102-1 through 102-m. In this conventional example, the same value as the n-th bit storage data stored in the data cells 110-j-1 through 110-j-n of the corresponding primary associative memory word 109-j is stored in the data cells 113-j-1 through 113-j-n as the n-bit secondary storage data.
Referring to FIG. 14, the associative memory 103 for primary searching operation of a first through m-th words n-bit configuration in the first through m-th words n-bit conventional associative memory 100 will be described. The associative memory 103 for primary searching operation of a first through m-th words n-bit configuration comprises the n-bit primary associative memory words 109-1 through 109-m, resisters 121-1 through 121-n, and inverted logical gates 122-1 through 122-n. The j-th (where j is an integer variable between 1 and m, both inclusive) primary associative memory word 109-j comprises first through n-th associative memory cells 118-j-1 through 118-j-n. The j-th primary associative memory word 109-j is connected to a corresponding data word line 115-j and a corresponding mask word line 117-j as input lines, and to a corresponding primary match line 116-j and matched data intermediate logical lines 114-1 through 114-n as output lines, and to the first through the n-th primary bit lines 105-1 through 105-n as data input/output lines.
A associative memory cell 118-j-k of a k-th digit (k is an integer variable between 1 and n, both inclusive) of the j-th primary associative memory word 109-j is connected to the corresponding data word line 115-j and the corresponding mask word line 117-j as input lines, and to the corresponding primary match line 116-j and a corresponding matched data intermediate logic line 114-k as output lines, and to a primary bit line 105-k as data input/output lines.
The associative memory cell 118-j-k comprises a data cell 110-j-k, a comparator 119-j-k, a mask cell 111-j-k, and a logical gate 120-j-k. The data cell 110-j-k is for storing “data” bit information at a corresponding bit of storage data supplied from an external source through the primary bit line 105-k. The comparator 119-j-k is for comparing the “data” bit information memorized in the data cell 110-j-k and the “search” bit information supplied through the primary bit line 105-k from the external source. The mask cell 111-j-k is for storing “mask” bit information of a corresponding bit of mask information supplied from the external source through the primary bit line 105-k. Herein, when the bit information stored in the mask cell 111-j-k is in a valid state for mask information, an invalid state for storage data is stored in corresponding data cell 110-j-k.
In this embodiment, a valid state and an invalid state for the mask information are represented by “0” and “1”, respectively and a valid state and an invalid state for the storage data are represented by “1” and “0”, respectively. Similar to the storage data, a valid state and an invalid state are represented by “1” and “0”, respectively, for the intermediate data lines 106-1 through 106-n. A valid state and an invalid state are represented by “1” and “0”, respectively, for the primary match lines 116-1 through 116-m, the secondary match lines 126-1 through 126-m, and the match lines 102-1 through 102-m.
The data cell 110-j-k stores as the storage data the state on the corresponding primary bit line 105-k on which the write data is driven when a corresponding data word line 115-j is in a valid state, or supplies the storage data stored therein to the corresponding primary bit line 105-k on which the write data is not driven when a corresponding data word line 115-j is in a valid state. When the corresponding data word line 115-j is in an invalid state, no operation is performed for the corresponding primary bit line 105-k. Irrespective of the state of the corresponding data word line 115-j, the storage data stored therein is supplied to the comparator 119-j-k and the logical gate 120-j-k in the same associative memory cell 118-j-k.
The mask cell 111-j-k stores as the mask information the state on a corresponding primary bit line 105-k on which the write data is driven when a corresponding mask word line 117-j is in a valid state, or supplies the mask information stored therein to the corresponding primary bit line 105-k on which the write data is not driven when a corresponding mask word line 117-j is in a valid state. When the corresponding mask word line 117-j is in an invalid state, no operation is performed for the corresponding primary bit line 105-k. Irrespective of the state of the corresponding mask word line 117-j, the mask information stored therein is supplied to the comparator 119-j-k in the same associative memory cell 118-j-k.
Prior to the primary searching operation, the primary match lines 116-1 through 116-m are precharged to a high level to be put into a valid state “1”.
The comparator 119-j-k is supplied with the value of the search data on the corresponding primary bit line 105-k, the storage data stored in the data cell 110-j-k, and the mask information stored in mask cell 111-j-k, in the same associative memory cell 118-j-k. When the mask information is in a valid state “0” or when the value on the corresponding primary bit line 105-k and the storage data in the data cell 110-j are coincident with each other, the corresponding primary match line 116-j is put into an opened state. Otherwise, the comparator 119-j-k puts the primary match line 116-j into an invalid state “0”. Thus, the wired AND logic connection with a valid state “1” for the primary match line 116 as true is achieved such that, when all the comparators 119-j-1 through 119-j-n, n in number, in the j-th primary associative memory word 109-j render the primary match line 116-j in an opened state, the primary match line 116-j is put into a valid state “1”, and otherwise into an invalid state “0”. In other words, upon the primary searching operation, only when all of the storage data stored in a primary associative memory word 109-j is completely coincident with the value of the primary bit lines 105-1 through 105-n except those bits excluded from a comparison object by the mask valid state “0” in the corresponding mask information, the primary match line 116-j is put into a valid state “1”, and otherwise, into an invalid state “0”.
The logical gate 120-j-k supplies an invalid state “0” of the intermediate data line 106 to the corresponding matched data intermediate logic line 114-k when the primary match line 116-j in the same primary associative memory word 109-j is in a valid state “1” and the storage data stored in the corresponding data cell 110-j-k in the same associative memory cell 118-j-k is in a valid state “1” for the storage data. Otherwise, the logical gate 120-j-k puts the matched data intermediate logic line 114-k into an opened state. The matched data intermediate logic line 114-k (where k is an integer variable between 1 and n, both inclusive) is put into a valid state “1” for the intermediate data line 106 through a resister 121-k. The matched data intermediate logic line 114-k is connected to all of the corresponding logical gates 120-1-k through 120-m-k, m in number, by a wired logic connection. Thus, when all of the connected logical gate 120-1-k through 120-m-k, m in number, render the matched data intermediate logic line 114-k in an opened state, the matched data intermediate logic line 114-k is put into a valid state “1” for the intermediate data line 106, and otherwise into an invalid state “0” for the intermediate data line 106.
Each of the inverted logical gates 122-1 through 122-n supplies an inverted value of the corresponding matched data intermediate logic lines 114-1 through 114-n to the corresponding intermediate data lines 106-1 through 106-n.
Therefore, the intermediate data line 106-k is supplied with a result of a logical sum operation, with a valid state for the storage data as true, of all the storage data stored in the corresponding data cells 110-1-k through 110-m-k in all of the k-th bit associative memory cells 118-1-k through 118-m-k which have the primary match lines 116-1 through 116-m that are in a valid state “1” upon completion of the primary searching operation by the inverted logical gate 122-k, the resister 121-k, the matched data intermediate logic line 114-k, and corresponding logical gates 120-1-k through 120-m-k, m in number. In this embodiment, the intermediate data line 106-k is supplied with a result of a logical sum operation with the valid state “1” for the storage data as true. As mentioned above, upon completion of the primary searching operation, the intermediate data lines 106-1 through 106-n are supplied with the same value of the storage data coincident with the search data 101 that has the least number of bits in an invalid state “0”.
Referring to FIG. 15, the associative memory 104 for secondary searching operation of a first through m-th words n-bit configuration in the conventional associative memory 100 of a first through m-th words n-bit will be described. The associative memory 104 for secondary searching operation of a first through m-th words n-bit configuration comprises secondary associative memory words 112-1 through 112-m. A j-th secondary associative memory word 112-j (where j is an integer variable between 1 and m, both inclusive) comprises associative memory cells 123-j-1 through 123-j-n, n in number. The secondary associative memory word 112-j is connected to the corresponding data word line 125-j as input lines, to the corresponding secondary match line 126-j as output lines, and to the secondary bit lines 108-1 through 108-n, n in number as data input/output lines.
An associative memory cell 123-j-k (where k is an integer variable between 1 and n, both inclusive) of the k-th bit of the j-th secondary associative memory word 112-j is connected to the corresponding data word line 125-j as input lines, to the corresponding secondary match line 126-j as the output lines, and to the secondary bit line 108-k as data input/output line.
The associative memory cell 123-j-k comprises a data cell 113-j-k and a comparator 124-j-k. The data cell 113-j-k is for storing “data” bit information at a corresponding bit of the secondary storage data supplied from the external source through the secondary bit line 108-k. The comparator 124-j-k is for comparing the “data” bit information stored in the data cell 113-j-k and “search” bit information supplied from the external source through the secondary bit line 108-k.
The data cell 113-j-k stores as the secondary storage data the state on a corresponding secondary bit line 108-k on which the write data is driven when a corresponding data word line 125-j is in a valid state, or supplies the storage data stored therein to the corresponding secondary bit line 108-k on which the write data is not driven when a corresponding data word line 125-j is in a valid state. When the corresponding data word line 125-j is in an invalid state, no operation is performed for the corresponding secondary bit line 108-k. Irrespective of the state of the corresponding data word line 125-j, the secondary storage data stored therein is supplied to the comparator 124-j-k in the same associative memory cell 123-k.
Prior to the secondary searching operation, the secondary match lines 126-1 through 126j are precharged to a high level to be put into a valid state “1”.
The comparator 124-j-k is supplied with the value of the search data on the corresponding secondary bit line 108-k and the secondary storage data stored in the data cell 113-j-k in the same associative memory cell 123-j-k. When the value of the secondary bit line 108-k and the secondary storage data stored in the data cell 113-j-k are coincident with each other, the comparator 124-j-k puts the secondary match line 126-j into an opened state, and otherwise, into an invalid state “0”. Thus, the wired AND logic connection with the valid state “1” for the secondary match line 126 as true is achieved such that, when all the comparators 124-j-1 through 124-j-n, n in number, in the j-th secondary associative memory word 112-j render the secondary match line 126-j in an opened state, the secondary match line 126-j is put into a valid state “1”, and otherwise, into an invalid state “0”. In other words, upon the secondary searching operation, only when all of the secondary storage data stored in the secondary associative memory word 112-j are completely coincident with the values of the secondary bit lines 108-1 through 108-k, the secondary match line 126-j is put into a valid state “1”, and otherwise into an invalid state “0”.
(Operation of the Conventional Associative Memory)
Next, referring to FIG. 16, description will be made about the operation when the above-mentioned conventional associative memory 100 is used in calculating the transfer network address in the network device 400-1 in FIG. 11. It is therefore assumed that the associative memory 100 comprises a first through fifth words nine-bit configuration in FIG. 16.
The associative memory 100 memorizes the connection information of the network device 400-1 in FIG. 11 in each of the primary associative memory words 109-1 through 109-5 as the storage data and the mask information. Herein, when a digit of a network address is represented by the symbol “*” as “don't care”, the corresponding bit of the storage data is stored with an invalid state “0” for the storage data, and the corresponding bit of the mask information is stored with a valid state “0” for the mask information.
Specifically, the primary associative memory word 109-1 stores in binary numbers notation the storage data “010.000.000” and the mask information “111.000.000” to represent the network address (2.*.*) for the segment 2 in the form of structured data. Similarly, the primary associative memory word 109-2 stores in binary numbers notation the storage data “011.000.000” and the mask information “111.000.000” to represent the network address (3.*.*) for the segment 3 in the form of structured data. The primary associative memory word 109-3 stores in binary numbers notation the storage data “001.010.000” and the mask information “111.111.000” to represent the network address (1.2.*) for the segment 4 in the form of structured data. The primary associative memory word 109-4 stores in binary numbers notation the storage data “001.011.000” and the mask information “111.111.000” to represent the network address (1.3.*) for the segment S in the form of structured data. The primary associative memory word 109-5 stores in binary numbers notation the storage data “010.110.000” and the mask information “111.111.000” to represent the network address (2.6.*) for the segment 6 in the form of structured data.
Further, the secondary associative memory words 112-1 through 112-5 of the associative memory 104 for secondary searching operation store the same value as the storage data of the corresponding primary associative memory words 109-1 through 109-5 as the secondary storage data. Therefore, the secondary associative memory word 112-1 stores in binary numbers notation “010.000.000”; the secondary associative memory word 112-2, in binary numbers notation “011.000.000”; the secondary associative memory word 112-3, in binary numbers notation “001.010.000”; the secondary associative memory word 112-4, in binary numbers notation “001.011.000”; and the secondary associative memory word 112-5, in binary numbers notation “010.110.000”, respectively.
Prior to the primary searching operation, all of the primary match lines 116-1 through 116-5 are precharged to a high level to be put into a valid state “1”. Further, prior to the secondary searching operation, all of the secondary match lines 126-1 through 126-5 are precharged to a high level to be put into a valid state “1”.
Description will proceed to the searching operation by supplying as the search data 101 the network address (2.6.5) in octal numbers notation, of the user's terminal 401-3 in FIG. 11.
The value “010.110.101” in binary numbers notation of nine bits of the search data 101 is supplied to the nine primary bit lines 105-1 through 105-9, and the associative memory 103 for primary searching operation carries out the primary searching operation. As a result, (2.*.*) in octal numbers notation stored in the primary associative memory word 109-1 and (2.6.*) in octal numbers notation stored in the primary associative memory word 109-5 are coincident with the search data on the primary bit lines 105-1 through 105-9. Accordingly, as a result of the primary searching operation, two primary match lines 116-1 and 116-5 are put into a valid state “1”, and the remaining primary match lines 116-2, 116-3, and 116-4 are put into an invalid state “0”.
Herein, the intermediate data line 106-1 produces the logical sum “0”, with “1” as true, of the storage data “0”, and “0” in the primary associative memory words 109-1 and 109-5 at bit positions corresponding to the intermediate data line 106-1. The intermediate data line 106-2 produces the logical sum “1”, with “1” as true, of the storage data “1”, and “1” in the primary associative memory words 109-1 and 109-5 at bit positions corresponding to the intermediate data line 106-2. Likewise, the intermediate data line 106-3, 106-4, 106-5, 106-6, 106-7, 106-8, and 106-9 produce the logical sum “0” of “0” and “0”, logical sum “1” of “0” and “1”, logical sum “1” of “0” and “1”, logical sum “0” of “0” and “0”, logical sum “0” of “0” and “0”, logical sum “0” of “0” and “0”, and logical sum “0” of “0” and “0”, respectively, with “1” as true. As a result, the intermediate data 107 is supplied with “010110000” in binary numbers notation.
The value of the intermediate data 107 is supplied to the secondary bit lines 108-1 through 108-9, and the associative memory 104 for secondary searching operation carries out a secondary searching operation. As a result, only the binary notation “010110000” stored in the secondary associative memory word 112-5 is completely coincident with the state on the secondary bit lines 108-1 through 108-9. Only the secondary match line 126-5 is therefore put into a valid state “1”, and the remaining secondary match lines 126-1, 126-2, 126-3, and 126-4 are put into an invalid state “0”. Thus, the associative memory 100 puts only the match line 102-5 into a valid state “1”.
It will therefore be understood that, in the match line 102 corresponding to one of the storage data coincident with the search data 101 taking the mask information into account, the conventional associative memory 100 can put only the match line 102-5 corresponding to the storage data with the least number of bits into a mask valid state for the mask information into a valid state. It will further be understood that, even when one clock time is required for the primary searching operation and the secondary searching operation, respectively, by a clock signal (not shown), since the conventional associative memory 100 comprises the associative memory 103 for primary searching operation for carrying out the primary searching operation, and the associative memory 104 for secondary searching operation for carrying out the associative memory for secondary searching operation, independently, it is possible to carry out the calculation of the transfer network address by supplying the search data 101 for every clock.
In the conventional associative memory 100 of a first through m-th words n-bit configuration mentioned above, since the n-bit intermediate data 107 produced by the associative memory 103 for primary searching operation of a first through m-th words n-bit configuration is supplied to the associative memory 104 for secondary searching operation, the associative memory 104 for secondary searching operation is required to be a first through m-th words n-bit configuration.
Herein, the data cells 110-1-1 through 110-m-n and the mask cells 111-1-1 through 111-m-n in the associative memory 103 for primary searching operation, and the data cells 113-1-1 through 113-m-n of the associative memory 104 for secondary searching operation can be comprised of typical SRAMs (Static Random Access Memory) comprising six MOS transistors. In this case, the area of each MOS transistor that composes the SRAM is similar to the circuit area of the minimum MOS transistor for manufacturing the conventional associative memory 100, in general.
However, as illustrated in FIG. 14, the primary match line 116-j is connected to the comparators 119-j-1 through 119-j-n in the first through n-th associative memory cells 118-j-1 through 118-j-n by a wired AND logic connection so that the primary match line 116-j requires enough length to achieve this connection. Thus, the parasitic capacitance of the primary match lines 116-1 through 116-m is very large, so that MOS transistors that compose the comparator 119 require large circuit area in order to drive the large parasitic capacitances of each of the primary match lines 116. For example, in a case of 0.25 micron meter rule manufacturing process, the wiring length is required about 1 millimeter in order to connect to 64 associative memories 118, so that the parasitic capacitance of each primary match lines 116 is about 0.3 pF. Accordingly, the size of each transistor that drives above-mentioned capacitance requires about 10 to 30 times as large as the size of the minimum MOS transistor for the manufacturing process. Likewise, as illustrated in FIG. 15, the secondary match line 126-j is connected to the first through n-th associative memory cells 123-j-1 through 123-j-n by a wired AND logic connection so that the size of each MOS transistor that composes the comparator 124 requires about 10 to 30 times as large as the size of the minimum MOS transistor for the manufacturing process. Further, as illustrated in FIG. 14, the matched data intermediate logic line 114-k is also connected to the logical gates 120-1-k through 120-m-k in the first to the m-th primary associative memory words 109-1 through 109-m by a wired AND connection so that the size of each MOS transistor that composes the logical gates 120 requires about 10 to 30 times as large as the size of the minimum MOS transistor for the manufacturing process.
Herein, if it is assumed that the circuit area of each MOS transistor that composes the comparator 119, the comparator 124, and the logical gate 120 requires 10 times as large as the circuit area of the minimum MOS transistor, and if it is further assumed that the comparator 119 comprises four MOS transistors, the comparator 120 comprises three MOS transistors, and the logical gate 120 comprises two MOS transistors, then the circuit area of the associative memory cell 118 that composes the associative memory 103 for primary searching operation is 72 times as the circuit area of the minimum MOS transistor, and the circuit area of the associative memory cell 123 that composes the associative memory 104 for secondary searching operation is 36 times as the circuit area of the minimum MOS transistor.
Therefore, in the conventional associative memory 100 of a first through m-th words n-bit configuration, both the associative memory 103 for primary searching operation and the associative memory 104 for secondary searching operation comprise a first through m-th words n-bit configuration associative memory, so that, irrespective of the bit width of the search data 101, the total circuit area excluding the associative memory 103 for primary searching operation requires 0.5 times as the circuit area of the associative memory 103 for primary searching operation.
In the meanwhile, only the n primary match lines, n in number having the same bit length as that of the mask information among the primary match lines 116-1 through 116-m, m in number maintain a valid state upon completion of the primary searching operation at the maximum, and the remaining primary match lines, (m-n) in number discharge the charge that has been precharged to a valid state before searching operation. Only one secondary match line among the secondary match lines 126-1 through 126-m, m in number, maintains a valid state upon completion of the secondary searching operation, and the remaining secondary match lines, (m-1) in number discharge the charge that has been precharged to a valid state before searching operation Therefore, if the associative memory comprises the first through 32768th 64-bit associative memory words, the parasitic capacitance corresponding to 65,471 lines at the minimum in sum of the primary match lines 116 and the secondary match lines 126 requires being precharged as given by (32,768−64)+(32,768−1)=65,471 for every searching operation. The numbers of the matched data intermediate logic lines 114-1 through 114-n, the primary bit lines 105-1 through 105-n, and the secondary bit lines 108-1 through 108-n are n in number, respectively, and since the number is 192 in total in the above-mentioned example, the parasitic capacitance can be negligible. In other words, power consumption of the conventional associative memory 100 mainly comprises the power that is consumed when the primary match line 116 and the secondary match line 126 are precharged for every searching operation. Herein, if the associative memory is produced using 0.25 micron meter rule manufacturing process and comprises the first through 32768th 64-bit associative memory words, the parasitic capacitance per one line of the primary match line 116 and the secondary match line 126 is about 0.3 pF as mentioned above, respectively. Accordingly, if it is assumed that the supplied voltage is 2.5 V and the searching period is 20 ns, then the power consumption of the whole chip is very large as given by(0.3 pF×2.5 V)/20 ns×2.5 V×65,471=6.14 W.
Therefore, the network device where the conventional associative memory 100 is used in calculating the transfer network address has also very large power consumption.
The Japanese Patent Application No. 3191737 also describes the configuration where while the associative memory for primary searching operation is provided with n-bit selection means and n-bit memory means, the associative memories for primary and secondary searching operations share their components with each other without increasing the number of the transistors of the associative memory for primary searching operation by controlling the operation of the comparator in each associative memory cell. In this case, although the problems of a large chip size and high power consumption are solved, the search data 101 cannot be supplied for every clock in order that the primary searching operation and the secondary searching operation share the same component with each other, and the execution speed of calculating the transfer network address is further decreased than that of the above-mentioned associative memory 100 by ½ or more.
It is therefore an object of the present invention to provide an associative memory which can perform the operation for every clock to produce the signal identifying, among the storage data coincident with the search data, particular storage data corresponding to the mask information with the least number of bits in a valid state, and has large storage capacity per unit of chip area.
It is another object of the present invention to provide an associative memory which can perform the operation for every clock to produce the signal identifying, among the storage data coincident with the search data, particular storage data corresponding to the mask information with the least number of bits in a valid state, and has small power consumption.
It is still another object of the present invention to reduce the power consumption of the network device, and provide a network system capable of transferring data at a high speed.